COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00013 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.cb On sequence extrapolation as an AI problem

	This idea came up in a discussion with Gray Clossman, who
is interested in sequence extrapolation as an AI problem.

	Many people have proposed sequence extrapolation as a
prototype AI problem.  The idea is that a person's life is a sequence
of sensory stimuli, and that science consists of inventing ways of
predicting the future of this sequence.
To this end many sequence extrapolating programs have been written
starting with those that predict sequences of integers by taking
differences and determining the co-efficients of a polynomial.

	It has always seemed to me that starting this way distorts
the heuristic character of both common sense and science.  Both of
them think about permanent aspects of the world and use the sequence
of sense data only to design and confirm hypotheses about these
permanent aspects.  The following sequence problem seems to me to
typify the break between hypotheses about the world and sequence
extrapolation.

The ball bouncing in the rectilinear world - roofs and boxes

	Suppose there is a rectangular two dimensional room.  In this
room are a number of objects having the form of rectangles.
A ball moves in the room with
constant velocity but bounces with angle of incidence equal to angle
of reflection whenever it hits a wall or an object.  The observer
cannot see the objects or the walls.  All he sees is the x-co-ordinate
of the ball at integer times but only when the ball is visible from
the front of the room.  This provides him with a sequence of numbers
which he can try to extrapolate.  Until the ball bounces off something
or goes under something, linear extrapolation works.

	Suppose first that the observer knows that he is dealing
with this kind of ball-in-room problem and only doesn't know the
locations of the objects and the walls.  After he has observed
the situation for a while he will have partial information about
the objects and their locations.  For example, he may note that
he has never been in a certain part of the room so there may
be unknown objects there.  Also he may have three sides of a
certain rectangle but may not know the fourth side, because he
has never bounced of that side yet.  He may extrapolate that
he won't have the opportunity of bouncing off that side for
a long time.

	Alternatively we may suppose that the observer doesn't
initially know about balls bouncing off rectangles but only knows
the sequence and must infer this using a general sequnce extrapolation
mechanism.  Our view is that this observer, whether human or machine,
can make progress only by guessing the underlying model.  At first
he may imagine a one dimensional bouncing model, but this will be
refuted the first time the ball doesn't bounce at an x-co-ordinate
where it has previously bounced.  Indeed he has to keep open
the possibility that the room is really 3  or more dimensional or that
more general objects than rectangles exist.

	We can elaborate the problem by supposing that when the
ball bounces off the front wall, the experimenter can put a paddle
at an angle and determine the angly of bounce so as to cause the
ball to enter regions where more information is wanted.

	Assuming the rectangles having edges parallel to the axes
makes the problem easier in an obvious sense but more difficult
in the sense that there is less interaction between the observable
x-co-ordinate and the unobservable y-co-ordinate.

	It would be interesting to determine the condition on
the x-path that distinguishes 2-dimensional from 3-dimensional
worlds, if there is one.  Unless we assume that the room has some
limited size, there need be no distinction.  Thus we must make
the never-fully-verified assumption that some of the repetititions
in sequences of bounces are because the ball hit the front or
back wall and bounced again off the same surfaces rather than
similar surfaces further back.

	I am skeptical that an AI program fundamentally based on the
idea of sequence extrapolation is the right idea here.  Donald Michie
suggests that the "domain experts" for this kind of problem of
inferring a mechanism that produces a sequence are cryptanalysts and
recommends a retired cryptanalyst who might be helpful.

John Kelley accepted (on Nov 24, 1980) the following cS206 problem

	Write a LISP program to implement the following functions:

(a t) gives 0 if the ball is invisible at time t
	    1 if the ball is moving to the right at t
	    2 if the ball is moving to the left at t

(b) initializes the ball

(c) gets a new configuration at random

(d t) gives the x-component of the velocity at time t

(save x) stores the configuration as the LISP variable x

(restore x) loads the configuration from the LISP variable x

	Here is one way of implementing the function that finds position
and velocity as a function of time.  It is necessary to go forward or
backward from a time when these things are known.

	1. Each edge of a rectangle is represented by a pair of functions
x = x0 + u0*s, y = y0 + v0*s together with limits s0 and s1.

	2. The position of the ball is represented by x = x0' + u0'*(t - t0),
y = y0' + v0'*(t - t0) from the time t0 until the ball hits something.

	3. Compute the interstection of the trajectory with each edge and
eliminated those edges for which the values of s are out of range.

	4. Choose that intersection with the least value of t > t0.

	5. Reflect at that point and continue the process.

Linear programming techniques can probably give something more sophisticated,
but it won't be needed if we keep down the number of rectangles.

	Whether the ball is visible at a given time is computed similarly,
but for that it is worthwhile to have the back edges represented by giving
y as a function of x and scanning over the ranges of x to determine the
function to compare y with.

	Since it might be interesting to get someone to try to figure out
the rule of the sequence, I suggest you don't talk about the problem except
with people who agree not to talk.

Note of 1985 Dec 27

	The problem has been given the following standard form.  The
observer sees only a sequence of 0s and 1s according to whether the
ball is visible or not.  It is invisible when it goes under a roof.

This is SEQUEN[F80,JMC].